package com.example.demo.sort;

public class QuickSort {

    public static void sort(int[] arr) {
        //快速排序1.0版本
        quickSort1(arr, 0, arr.length);
    }


    /**
     * 快速排序1.0
     *
     * @param arr
     * @param left
     * @param right
     */
    public static void quickSort1(int[] arr, int left, int right) {
        if (left < right) {
            int index = partition1(arr, left, right);
            quickSort1(arr, left, index - 1);
            quickSort1(arr, index + 1, right);
        }

    }

    /**
     * 获取基线值的位置
     *
     * @param arr
     * @param left
     * @param right
     * @return
     */
    public static int partition1(int[] arr, int left, int right) {
        int temp = left;
        //小于值基线值的起始位置
        int index = temp + 1;
        for (int i = index; i <= right; i++) {
            if (arr[i] < arr[temp]) {
                swap(arr, i, index);
                index++;
            }
        }
        swap(arr, temp, index - 1);
        return index - 1;
    }


    /**
     * 快速排序2.0
     *
     * @param arr
     * @param left
     * @param right
     */
    public static void quickSort2(int[] arr, int left, int right) {
        if (left < right) {
            int[] index = partition2(arr, left, right);
            quickSort2(arr, left, index[0]-1);
            quickSort2(arr, index[1]+1, right);
        }

    }

    /**
     * 获取基线值的位置
     *
     * @param arr
     * @param left
     * @param right
     * @return
     */
    public static int[] partition2(int[] arr, int left, int right) {
//        int temp = left;
//        //小于值基线值的起始位置
//        int index = temp + 1;
//        while(){
//
//        }
//        for (int i = index; i <= right; i++) {
//            if (arr[i] < arr[temp]) {
//                swap(arr, i, index);
//                index++;
//            }
//        }
//        swap(arr, temp, index - 1);
//        return index - 1;
        return null;
    }






    /**
     * 交换
     * @param arr
     * @param i
     * @param j
     */
    public static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }


}
